<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>2264：Free Goodies</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">Free Goodies</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">Free Goodies</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                Free Goodies                </h1>
                <p>时间限制：1s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：128MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><p></p>
<p>Petra and Jan have just received a box full of free goodies, and want to divide the goodies between them. However, it is not easy to do this fairly, since they both value different goodies differently.</p>
<p>To divide the goodies, they have decided upon the following procedure: they choose goodies one by one, in turn, until all the goodies are chosen. A coin is tossed to decide who gets to choose the first goodie.</p>
<p>Petra and Jan have different strategies in deciding what to choose. When faced with a choice, Petra always selects the goodie that is most valuable to her. In case of a tie, she is very considerate and picks the one that is least valuable to Jan. (Since Petra and Jan are good friends, they know exactly how much value the other places on each goodie.)</p>
<p>Jan's strategy, however, consists of maximizing his own final value. He is also very considerate, so if multiple choices lead to the same optimal result, he prefers Petra to have as much final value as possible.</p>
<div class="p"><!----></div>
<p>You are given the result of the initial coin toss. After Jan and Petra have finished dividing all the goodies between themselves, what is the total value of the goodies each of them ends up with?</p>
<p></p>
<p></p>
<p>有两个人，分N个物品，每个物品分别对两个人有不同的价值。两个人每次轮流从未被拿走的物品中拿走一个物品。规则是第一个人每次是拿剩下物品中对他而言价值最高的那个，如果有相同的就会拿那个对另外一个人价值最低的物品。另一个人是每次拿那个能保证他最后能拿到价值最大的物品，当然如果有多种选项的话也会优先选择那个对另外一个人价值最低的物品。现在告诉你物品和谁先拿，问最后两人分别能拿到多少？</p></p><hr/><h3>输入格式</h3><p><p align="left"><font face="Times New Roman" size="3">On the first line a positive integer: the number of test cases, at most 100. After that per test case: </font></p>
<p>One line with an integer n (1 &le; n &le; 1&nbsp;000): the number of goodies.</p>
<p>One line with a string, either &quot;<tt><font face="NSimsun">Petra</font></tt>&quot; or &quot;<tt><font face="NSimsun">Jan</font></tt>&quot;: the person that chooses first.</p>
<p>n lines with two integers p<sub>i</sub> and j<sub>i</sub> (0 &le; p<sub>i</sub>,j<sub>i</sub> &le; 1&nbsp;000) each: the values that Petra and Jan assign to the i-th goodie, respectively</p></p><hr/><h3>输出格式</h3><p><p align="left"><font face="Times New Roman" size="3">Per test case: </font></p>
<p>One line with two integers: the value Petra gets and the value Jan gets. Both values must be according to their own valuations</p></p><hr/><h3>样例输入</h3><pre>3
4
Petra
100 80
70 80
50 80
30 50
4
Petra
10 1
1 10
6 6
4 4
7
Jan
4 1
3 1
2 1
1 1
1 2
1 3
1 4

</pre><hr/><h3>样例输出</h3><pre>170 130
14 16
9 10

</pre><hr/><h3>提示</h3><p>没有写明提示</p><hr/><h3>题目来源</h3><p>没有写明来源</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=2264" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=2264" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>